package backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * 全排列
 * @author le
 */
public class FullPermutation
{
    /// 底层使用双向队列

    List<List<Integer>> res = new LinkedList<>();

    public static void main(String[] args)
    {
        int[] nums = {1, 2, 3};
        FullPermutation permutation = new FullPermutation();
        List<List<Integer>> list = permutation.permute(nums);
        for (List<Integer> tmp : list){
            System.out.println(tmp.toString());
        }
    }

    public  List<List<Integer>> permute(int[] nums){
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;

    }

    public  void backtrack(int[] nums, LinkedList<Integer> track){
        if (track.size() == nums.length){
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length;i++){
            if (track.contains(nums[i])){
                continue;
            }
            track.add(nums[i]);
            backtrack(nums, track);
            track.removeLast();
        }
    }
}
